Stars and bars

Stars and bars (Stele și bare) este o metodă de rezolvare a unor probleme de combinatorică. Se poate folosi când trebuie să determinăm numărul de modalități de a grupa un număr dat de obiecte identice.

Teoremă: Numărul de a variante de a plasa n obiecte identice în k cutii este egal cu: \( C_{n+k-1}^{k-1} \).

Demonstrația implică separarea celor n obiecte (stele) în k cutii prin k-1 bare – de unde și numele. De exemplu, configurația următoare are n=7 stele și k=4 cutii: \( \star \vert \star \star \vert \vert \star \star \star \star \) și corespunde următoarei situații:

• prima cutie conține un obiect
• a doua cutie conține două obiecte
• a treia cutie nu conține niciun obiect
• a patra cutie conține patru obiecte

Configurația este echivalentă cu următoarea configurație de biți: 0100110000, în care bitul 1 corespunde obiectului, \( \star \), iar 1 corespunde barei, \( \vert \). Toate configurațiile convenabile au n-k+1 biți, dintre care n au valoarea 0 și k-1 au valoarea 1 și corespund submulțimilor cu k-1 elemente ale unei mulțimi cu n+k-1 elemente.

Astfel, numărul lor este \( C_{n+k-1}^{k-1} \).

Consecință Ecuația \(x_1 + x_2 + x_3 + \cdots + x_k = n\) are \( C_{n+k-1}^{k-1} \) soluții întregi nenegative (mai mari sau egale cu 0).

Afirmația este echivalentă cu teorema de mai sus, în care \(x_i\) fiind egal cu numărul de obiecte din cutia i.

Teoremă: Numărul de a variante de a plasa n obiecte identice în k cutii astfel încât fiecare cutie conține cel puțin un obiect este egal cu: \( C_{n-1}^{k-1} \).

Demonstrația 1: Fixăm în fiecare cutie câte un obiect. Rămân \(n – k\) obiecte care trebuie plasate în \(k\) cutii, în condițiile teoremei de mai sus. Astfel, numărul de variante este \( C_{n-k+k-1}^{k-1} = C_{n-1}^{k-1} \).

Demonstrația 2: Folosim metoda Stars and bars. Separarea obiectelor în cutii se face plasând \(k\) bare în golurile dintre obiecte. Sunt \(n-1\) goluri în care putem plasa \(k\) bare în \( C_{n-1}^{k-1} \) moduri.